package alg

import "fmt"

func ShellSortRun() {
	//定义一个数组
	arr := []int{3, 1, 12, 7, 17, 30, 15, 50, 55, 76, 75}
	ShellSort(arr)
	fmt.Println("main arr=", arr, "len=", len(arr))
}

// 希尔排序, 把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序
// 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至1时, 整个文件恰被分成一组, 算法便终止
// 适用于数据量在5000以下并且速度并不是特别重要的场合, 对于数据量较小的数列重复排序是非常好
// 平均时间复杂度 O(nlogn), 最坏的时间复杂度为 O(n^2)
func ShellSort(arr []int) {
	arrLen := len(arr)
	// 进行两两比较
	for gap := arrLen / 2; gap > 0; gap /= 2 {
		fmt.Println("每次 gap循环 gap = ,", gap)

		// 从第gap 元素开始, 逐个对其所在组进行直接插入排序操作
		for i := gap; i < arrLen; i++  {
			j := i
			fmt.Println("每组 gap循环 j = ,", j)
			for j - gap >= 0 && arr[j] < arr[j-gap] {
				fmt.Println("每次 j循环 gap = ,", gap, "left=", arr[j], "right=", arr[j-gap])
				arr[j], arr[j-gap] = arr[j-gap], arr[j]
				j -= gap
			}
		}
	}
}
